package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

//将搜索二叉树转换成双向链表：使用队列，二叉树中序遍历，存储到队列等容器中，随后按序重连所有节点。时间复杂O(n)，空间复杂O(n)
//使用递归，向树的深层遍历，把以X为头的左子树转换为有序双向链表，把以X为头的右子树转换为有序双向链表，通过X将两部分连接，
// 并返回双向链表的头和尾（即左子树头和右子树尾）作为向上层的左子树或右子树。时间复杂O(n)即二叉树节点个数n，空间复杂即O(h)二叉树高度h
//有一种遍历二叉树神级方法，时间复杂O(n)，空间复杂O(1)
public class ConvertTreeToDoubleLinkedList {

    static class Node{
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    static class ReturnType{
        private Node start;
        private Node end;

        public ReturnType(Node start,Node end){
            this.start = start;
            this.end = end;
        }

        public Node getStart() {
            return start;
        }

        public void setStart(Node start) {
            this.start = start;
        }

        public Node getEnd() {
            return end;
        }

        public void setEnd(Node end) {
            this.end = end;
        }
    }

    public void convertTreeToDoubleLinkedListByQueue(Node head){
        Queue<Node> queue = new LinkedList<>();
        recursive(head,queue);
        head = queue.poll();
        Node pre = head;
        Node cur = null;
        while(!queue.isEmpty()){
            cur = queue.poll();
            cur.setLeft(pre);
            pre.setRight(cur);
            pre = cur;
        }
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.getValue()).append(" ");
            head = head.getRight();
        }
        System.out.print(sb);
    }

    private void recursive(Node head,Queue<Node> queue){
        if(head == null){
            return;
        }
        recursive(head.getLeft(),queue);
        queue.offer(head);
        recursive(head.getRight(),queue);
    }

    public void convertTreeToDoubleLinkedList(Node head){
        if(head == null){
            return;
        }
        head = process(head).getStart();
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.getValue()).append(" ");
            head = head.getRight();
        }
        System.out.print(sb);
    }

    private ReturnType process(Node head){
        if(head == null){
            return new ReturnType(null,null);
        }
        ReturnType leftList = process(head.getLeft());
        ReturnType rightList = process(head.getRight());
        if(leftList.getEnd() != null){
            leftList.getEnd().setRight(head);
        }
        head.setLeft(leftList.getEnd());
        head.setRight(rightList.getStart());
        if(rightList.getStart() != null){
            rightList.getStart().setLeft(head);
        }
        return new ReturnType(leftList.getStart() != null ? leftList.getStart() : head,
                rightList.getEnd() !=null ? rightList.getEnd() : head);
    }




    public void createTree(Node node,int[][] arr){
        int left = arr[node.getValue()][0];
        int right = arr[node.getValue()][1];
        if(left != 0){
            Node leftNode = new Node(left);
            node.setLeft(leftNode);
            createTree(leftNode,arr);
        }
        if(right != 0){
            Node rightNode = new Node(right);
            node.setRight(rightNode);
            createTree(rightNode,arr);
        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        int[][] arr = new int[len + 1][2];
        String[] values = scanner.readLine().split(" ");
        int root = Integer.parseInt(values[0]);
        arr[root][0] = Integer.parseInt(values[1]);
        arr[root][1] = Integer.parseInt(values[2]);
        int index = 0;
        for(int i = 1;i < len;i++){
            values = scanner.readLine().split(" ");
            index = Integer.parseInt(values[0]);
            arr[index][0] = Integer.parseInt(values[1]);
            arr[index][1] = Integer.parseInt(values[2]);
        }
        Node node= new Node(root);
        new ConvertTreeToDoubleLinkedList().createTree(node,arr);
//        new ConvertTreeToDoubleLinkedList().convertTreeToDoubleLinkedListByQueue(node);
        new ConvertTreeToDoubleLinkedList().convertTreeToDoubleLinkedList(node);
    }
}
